package pers.qianyu.month_202011.date_20201126;

/**
 * 234. 回文链表
 * https://leetcode-cn.com/problems/palindrome-linked-list/
 *
 * @author mizzle rain
 * @date 2020-11-26 23:04
 */
public class IsPalindrome2 {
    /**
     * 快慢指针解法
     */
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, low = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            low = low.next;
        }
        if (fast != null) {
            low = low.next;
        }
        ListNode node = reverseNodeList(low);
        while (node != null && head != null) {
            if (node.val != head.val) {
                return false;
            }
            node = node.next;
            head = head.next;
        }
        return true;
    }

    private ListNode reverseNodeList(ListNode node) {
        if (node == null || node.next == null) {
            return node;
        }
        ListNode last = reverseNodeList(node.next);
        node.next.next = node;
        node.next = null;
        return last;
    }

    private ListNode reverseNodeList2(ListNode node) {
        ListNode p = node, newList = null;
        while (p != null) {
            ListNode temp = p.next;
            p.next = newList;
            newList = p;
            p = temp;
        }
        return newList;
    }


    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
